perm filename CMPLR.TOM[206,LSP] blob
sn#107930 filedate 1974-10-27 generic text, type T, neo UTF8
CS206
Handout #35
06-04-74
PDP-10
This handout contains some very basic (and somewhat
simplified) facts about the PDP-10. This information should
be sufficient to understand the output of the LCOM0 compiler.
The basic addressable unit of main memory is the
word, which is 36 bits in length. Addresses are 18 bits
in length. In instructions and in accumulators used as
index registers, the address field is found in the lower
18 bits of the word.
There are 16 accumulators. These registers may be
used as accumulators (to receive the results of calculations)
or as index registers (modifying the nominal addresses in
memory reference instructions to form effective addresses).
In addition, they are addressable as the first 16 locations
in memory.
The format of memory reference instructions is:
+--------+----+---+-----+---------------+
| opcode | ac | i | ndx | nominal addr |
+--------+----+---+-----+---------------+
9 4 1 4 18
The opcode specifies the operation to be performed. The ac is
a source or result accumulator. The i bit is set if addressing
is to be indirect. The ndx field specifies an index register.
Effective addresses are computed as follows. If ndx
is non-zero, then the effective address is the sum of the nominal
address and the contents of the AC specified by ndx. Otherwise,
the effective address is equal to the nominal address. If i
is set, then the same calculation is carried out on the contents
of the word specified by the effective address, and the result
becomes the effective address.
Throughout the following discussion of specific instructions,
AC is the accumulator, E the effective address and PC the program
counter. A parenthesized quantity indicates "contents of."
An r indicates right half word, an l left half word. Numbers are octal.
MOVE (AC) ← (E)
MOVEI (AC) ← E
MOVEM* (E) ← (AC)
PUSH (AC) ← (AC) + 1000001; ((ACr)) ← (E)
POP* (E) ← ((ACr)); (AC) ← (AC) - 1000001
PUSHJ* (AC) ← (AC) + 1000001; ((ACr)) ← (PC); (PC) ← E
POPJ (PC) ← ((ACr)r); (AC) ← (AC) - 1000001
JRST (PC) ← E
JUMPN if (AC) }= 0 then (PC) ← E
JUMPE if (AC) = 0 then (PC) ← E
ADD* (AC) ← (AC) + (E)
SUB (AC) ← (AC) - (E)
HRRZ (ACr) ← (Er); (ACl) ← 0
HLRZ (ACr) ← (El); (ACl) ← 0
Instructions marked with * do not appear in any of the examples.
They are included only for completeness.
In the stack instructions, the stack pointer is maintained in
the accumulator. The right half contains the actual stack pointer.
The left half contains a limit on the size of the stack.
(DEFPROP LC0FNS
(LC0FNS COMPL
COMP
PRUP
MKPUSH
COMPEXP
COMPLIS
LOADAC
COMCOND
COMBOOL
COMPANDOR)
VALUE)
~COMPL is the user-callable driver. It is a FEXPR. It takes as
~ an argument a single file name, which must have no extension.
~ EXPRs on a file called FILNAM will be compiled into LAP and
~ written on the file FILNAM.LAP. Other types of function
~ definitions and non-definitions are simply copied to output.
(DEFPROP COMPL
(LAMBDA(FILE)
(PROG (Z)
(EVAL
(CONS (QUOTE OUTPUT)
(CONS (QUOTE DSK:)
(LIST (CONS (CAR FILE) (QUOTE LAP))))))
(EVAL (CONS (QUOTE INPUT) (CONS (QUOTE DSK:) FILE)))
(INC T NIL)
LOOP (SETQ Z (ERRSET (READ)))
(COND ((ATOM Z) (GO DONE)))
(SETQ Z (CAR Z))
(COND ((OR (EQ (CAR Z) (QUOTE DE))
(AND (EQ (CAR Z) (QUOTE DEFPROP))
(EQ (CADDDR Z) (QUOTE EXPR))))
(PROG (PROG)
(SETQ PROG
(COND ((EQ (CAR Z) (QUOTE DE))
(COMP (CADR Z)
(CADDR Z)
(CADDDR Z)))
(T
(COMP (CADR Z)
(CADR (CADDR Z))
(CADDR (CADDR Z))))))
(OUTC T NIL)
(MAPC (FUNCTION PRINT) PROG)
(OUTC NIL NIL)
(PRINT (LIST (CADR Z) (LENGTH PROG)))))
(T (OUTC T NIL) (PRINT Z) (OUTC NIL NIL)))
(GO LOOP)
DONE (OUTC T NIL)
(OUTC NIL T)
(INC NIL T)
(RETURN (QUOTE ENDCOMP))))
FEXPR)
~COMP compiles a single function definition, returning a list of
~ the LAP code corresponding to the definition.
~ FN is the atomic name of the function being compiled.
~ VARS is the formal parameter list for the function.
~ EXP is the function body.
(DEFPROP COMP
(LAMBDA(FN VARS EXP)
((LAMBDA(N)
(APPEND (LIST (LIST (QUOTE LAP) FN (QUOTE SUBR)))
(MKPUSH N 1)
(COMPEXP EXP (MINUS N) (PRUP VARS 1))
(LIST
(LIST (QUOTE SUB) (QUOTE P) (LIST (QUOTE C) N 0 N 0)))
(QUOTE ((POPJ P) NIL))))
(LENGTH VARS)))
EXPR)
~PRUP returns an A-LIST formed by pairing successive elements of
~ VARS with consecutive integers beginning with N.
(DEFPROP PRUP
(LAMBDA(VARS N)
(COND ((NULL VARS) NIL)
(T (CONS (CONS (CAR VARS) N) (PRUP (CDR VARS) (PLUS N 1))))))
EXPR)
~MKPUSH returns a list of N (PUSH P i) instructions, where i runs
~ from M to M+N-1. Used to push arguments onto the stack.
(DEFPROP MKPUSH
(LAMBDA(N M)
(COND ((LESSP N M) NIL)
(T
(CONS (LIST (QUOTE PUSH) (QUOTE P) M)
(MKPUSH N (PLUS M 1))))))
EXPR)
~COMPEXP is the heart of LCOM0. It determines precisely
~ what an expression is, and compiles appropriate code
~ for it. It returns a list of that code.
~ EXP is the expression to be compiled.
~ M is minus the number of entries on the stack. When
~ added to a value retrieved from the A-LIST VPR, it
~ can be used to locate a variable on the stack.
~ VPR is an A-LIST, associating variable names with
~ numbers which, when added to M, give stack offsets.
~ Both M and VPR maintain these definitions throughout.
(DEFPROP COMPEXP
(LAMBDA(EXP M VPR)
(COND ((NULL EXP) (QUOTE ((MOVEI 1 0)))) ~NIL
((EQ EXP T) (QUOTE ((MOVEI 1 (QUOTE T))))) ~T
((ATOM EXP) ~variable
(LIST
(LIST (QUOTE MOVE)
1
(PLUS M (CDR (ASSOC EXP VPR)))
(QUOTE P))))
((OR (EQ (CAR EXP) (QUOTE AND)) ~boolean expression
(EQ (CAR EXP) (QUOTE OR))
(EQ (CAR EXP) (QUOTE NOT)))
((LAMBDA(L1 L2)
(APPEND
(COMBOOL EXP M L1 NIL VPR)
(LIST (QUOTE (MOVEI 1 (QUOTE T)))
(LIST (QUOTE JRST) 0 L2)
L1
(QUOTE (MOVEI 1 0))
L2)))
(GENSYM)
(GENSYM)))
((EQ (CAR EXP) (QUOTE COND)) ~COND
(COMCOND (CDR EXP) M (GENSYM) VPR))
((EQ (CAR EXP) (QUOTE QUOTE)) ~QUOTE
(LIST (LIST (QUOTE MOVEI) 1 EXP)))
((ATOM (CAR EXP)) ~function call
((LAMBDA(N)
(APPEND
(COMPLIS (CDR EXP) M VPR)
(LOADAC (DIFFERENCE 1 N) 1)
(LIST
(LIST (QUOTE SUB) (QUOTE P) (LIST (QUOTE C) N 0 N 0)))
(LIST
(LIST (QUOTE CALL)
N
(LIST (QUOTE E) (CAR EXP))
(QUOTE S)))))
(LENGTH (CDR EXP))))
((EQ (CAAR EXP) (QUOTE LAMBDA)) ~LAMBDA expression
((LAMBDA(N)
(APPEND
(COMPLIS (CDR EXP) M VPR)
(COMPEXP
(CADDAR EXP)
(DIFFERENCE M N)
(APPEND (PRUP (CADAR EXP) (DIFFERENCE 1 M)) VPR))
(LIST
(LIST (QUOTE SUB) (QUOTE P) (LIST (QUOTE C) N 0 N 0)))))
(LENGTH (CDR EXP))))
(T NIL))) ~oops
EXPR)
~COMPLIS compiles code to evaluate each expression in a list of
~ expressions and to push those values onto the stack. It
~ returns a list of that code. It is used to compile code
~ to evaluate arguments to called functions or LAMBDA expressions.
~ U is a list of expressions.
(DEFPROP COMPLIS
(LAMBDA(U M VPR)
(COND ((NULL U) NIL)
(T
(APPEND (COMPEXP (CAR U) M VPR)
(QUOTE ((PUSH P 1)))
(COMPLIS (CDR U) (DIFFERENCE M 1) VPR)))))
EXPR)
~LOADAC returns a list of (MOVE i j P) instructions, loading
~ consecutive accumulators from the top of the stack.
~ K indexes the accumulator loaded.
~ N indexes the stack offset.
(DEFPROP LOADAC
(LAMBDA(N K)
(COND ((GREATERP N 0) NIL)
(T
(CONS (LIST (QUOTE MOVE) K N (QUOTE P))
(LOADAC (PLUS N 1) (PLUS K 1))))))
EXPR)
~COMCOND compiles a COND.
~ U is a list of clauses in the COND.
~ L is a label to be emitted at the end of all code for
~ the COND.
(DEFPROP COMCOND
(LAMBDA(U M L VPR)
(COND ((NULL U) (LIST L))
(T
((LAMBDA(L1)
(APPEND (COMBOOL (CAAR U) M L1 NIL VPR)
(COMPEXP (CADAR U) M VPR)
(LIST (LIST (QUOTE JRST) L) L1)
(COMCOND (CDR U) M L VPR)))
(GENSYM)))))
EXPR)
~COMBOOL compiles code for a single predicate. That is, the
~ code generated evaluates the predicate and branches somewhere,
~ depending on the value.
~ P is the predicate.
~ L is a label which represents the branch point.
~ FLG is a flag. If FLG is NIL, code is to fall thru on non-NIL
~ result and branch to L on NIL result. If FLG is non-NIL,
~ code is to fall thru on NIL result and branch to L on
~ non-NIL result.
(DEFPROP COMBOOL
(LAMBDA(P M L FLG VPR)
(COND ((ATOM P) ~simple variable
(APPEND
(COMPEXP P M VPR)
(LIST
(LIST (COND (FLG (QUOTE JUMPN)) (T (QUOTE JUMPE))) 1 L))))
((EQ (CAR P) (QUOTE AND)) ~conjunction
(COND ((NOT FLG) (COMPANDOR (CDR P) M L NIL VPR))
(T
((LAMBDA(L1)
(APPEND (COMPANDOR (CDR P) M L1 NIL VPR)
(LIST (LIST (QUOTE JRST) 0 L))
(LIST L1)))
(GENSYM)))))
((EQ (CAR P) (QUOTE OR)) ~disjunction
(COND (FLG (COMPANDOR (CDR P) M L T VPR))
(T
((LAMBDA(L1)
(APPEND (COMPANDOR (CDR P) M L1 T VPR)
(LIST (LIST (QUOTE JRST) 0 L))
(LIST L1)))
(GENSYM)))))
((EQ (CAR P) (QUOTE NOT)) ~negation
(COMBOOL (CADR P) M L (NOT FLG) VPR))
(T ~other expression
(APPEND
(COMPEXP P M VPR)
(LIST
(LIST (COND (FLG (QUOTE JUMPN)) (T (QUOTE JUMPE)))
1
L))))))
EXPR)
~COMPANDOR compiles code for lists of predicates connected
~ conjunctively or disjunctively.
~ U is a list of predicates.
~ L is a label.
~ FLG is a flag. If FLG is NIL, we are to fall thru on non-NIL
~ results and branch to L on NIL results (AND case). If FLG
~ is non-NIL, we are to fall thru on NIL results and branch
~ to L on non-NIL results (OR case).
(DEFPROP COMPANDOR
(LAMBDA(U M L FLG VPR)
(COND ((NULL U) NIL)
(T
(APPEND (COMBOOL (CAR U) M L FLG VPR)
(COMPANDOR (CDR U) M L FLG VPR)))))
EXPR)
For the file containing:
(DEFPROP DROPFN
(DROPFN DROP)
VALUE)
(DEFPROP DROP
(LAMBDA(X)
(COND ((NULL X) NIL) (T (CONS (LIST (CAR X)) (DROP (CDR X))))))
EXPR)
***************************************************************************
LCOM0 procuces the following code:
(DEFPROP DROPFN (DROPFN DROP) VALUE)
(LAP DROP SUBR)
(PUSH P 1)
(MOVE 1 0 P)
(PUSH P 1)
(MOVE 1 0 P)
(SUB P (C 1 0 1 0))
(CALL 1 (E NULL) S)
(JUMPE 1 G0163)
(MOVEI 1 0)
(JRST G0162)
G0163
(MOVEI 1 (QUOTE T))
(JUMPE 1 G0164)
(MOVE 1 0 P)
(PUSH P 1)
(MOVE 1 0 P)
(SUB P (C 1 0 1 0))
(CALL 1 (E CAR) S)
(PUSH P 1)
(MOVE 1 0 P)
(SUB P (C 1 0 1 0))
(CALL 1 (E LIST) S)
(PUSH P 1)
(MOVE 1 -1 P)
(PUSH P 1)
(MOVE 1 0 P)
(SUB P (C 1 0 1 0))
(CALL 1 (E CDR) S)
(PUSH P 1)
(MOVE 1 0 P)
(SUB P (C 1 0 1 0))
(CALL 1 (E DROP) S)
(PUSH P 1)
(MOVE 1 -1 P)
(MOVE 2 0 P)
(SUB P (C 2 0 2 0))
(CALL 2 (E CONS) S)
(JRST G0162)
G0164
G0162
(SUB P (C 1 0 1 0))
(POPJ P)
NIL
LCOM4 produces the following code:
(DEFPROP DROPFN (DROPFN DROP) VALUE)
(LAP DROP SUBR)
(PUSH P 1)
(MOVE 1 0 P)
(JUMPE 1 G0162)
(HLRZ@ 1 0 P)
(CALL 1 (E LIST) S)
(PUSH P 1)
(HRRZ@ 1 -1 P)
(CALL 1 (E DROP) S)
(MOVE 2 1)
(MOVE 1 0 P)
(SUB P (C 1 0 1 0))
(CALL 2 (E CONS) S)
G0162
(SUB P (C 1 0 1 0))
(POPJ P)
NIL
***************************************************************************
ILISP COMPILER produces the following code:
(DEFPROP DROPFN (DROPFN DROP) VALUE)
(LAP DROP SUBR)
(PUSH P 1)
(JUMPE 1 TAG1)
(HLRZ@ 1 0 P)
(CALL 1 (E NCONS) S)
(PUSH P 1)
(HRRZ@ 1 -1 P)
(CALL 1 (E DROP) S)
(POP P 2)
(CALL 2 (E XCONS) S)
TAG1 (SUB P (C 1 0 1 0))
(POPJ P)
NIL